package com.kk.datastructure.tree.availabletree.huffman;
//package com.kk.datastructure.tree.availabletree;
//import java.util.ArrayList;
//import java.util.Collections;
//import java.util.List;
//
///**
// * title: 赫夫曼树实现
// * @author 阿K
// * 2021年1月3日 下午5:43:07 
// */
//public class HuffmanTree {
//
//	public static void main(String[] args) {
//
//		int arr[] = { 13, 7, 8, 3, 29, 6, 1 };
//		Node root = createHuffmanTree(arr); 
//
//		System.out.println("---------美丽的分割线-----------");
//		// 测试
//		preOrder(root);
//	}
//	
//	// 前序遍历
//	public static void preOrder(Node root) {
//		if(root!=null) {
//			root.preOrder();
//		}else {
//			System.out.println("改二叉树为空，前序遍历的鸡毛？？");
//		}
//	}
//
//	/**
//	 * 创建赫夫曼树
//	 * 
//	 * @param arr 需要被构建成的数组
//	 * @return 返回 赫夫曼树 的 root节点
//	 */
//	public static Node createHuffmanTree(int[] arr) {
//		// 【1】将要数组转换为节点
//		// (1)遍历arr数组
//		// (2)将arr数组的每个元素构建成 Node
//		// (3)将 所有 Node 放入 ArrayList 中
//		List<Node> nodes = new ArrayList<>();
//		for (int value : arr) {
//			nodes.add(new Node(value));
//		}
//
//		// 【2】循环处理分析得四步骤，故，最终返回的只有一个 root 节点
//		while (nodes.size() > 1) {// 逐步递减，直到只有一个节点为止(既root
//			// 1、从小到大排序(每次循环都要排序一次)
//			Collections.sort(nodes);
//
//			System.out.println("nodes =" + nodes);
//
//			// 2、取出根节点权值最小的两颗二叉树，然后合并
//			// <1> 取出权值最小的节点（二叉树）
//			Node leftNode = nodes.get(0);
//			// <2> 取出权值次小(第二小)的节点（二叉树）
//			Node rightNode = nodes.get(1);
//			// <3> 合并成一颗新的二叉树
//			Node parent = new Node(leftNode.value + rightNode.value);
//			parent.left = leftNode;
//			parent.rigth = rightNode;
//
//			// 3、从 nodes 集合中删除已经处理过的二叉树
//			nodes.remove(leftNode);
//			nodes.remove(rightNode);
//
//			// 4、将 合并出来的二叉树 parent 加入到 nodes集合中
//			nodes.add(parent);
//		}
//
//		// 【3】返回赫夫曼树的 root 节点
//		return nodes.get(0);
//	}
//
//}
//
//// 节点类 
//// 实现Comparable接口排序
//class Node implements Comparable<Node> {
//
//	int value; // 节点权值
//	Node left; // 指向左子节点
//	Node rigth; // 指向右子节点
//
//	public Node(int value) {
//		super();
//		this.value = value;
//	}
//
//	// 前序遍历
//	public void preOrder() {
//		System.out.println(this);
//
//		if (this.left != null) {
//			this.left.preOrder();
//		}
//
//		if (this.rigth != null) {
//			this.rigth.preOrder();
//		}
//	}
//
//	@Override
//	public int compareTo(Node o) {
//		// 表示从小到大排序
//		return this.value - o.value;
//	}
//
//	@Override
//	public String toString() {
//		return "Node [value=" + value + "]";
//	}
//
//}
